package 链表题目;

import 链表题目.model.ListNode;


//反转链表
//https://leetcode.cn/problems/reverse-linked-list/description/
//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
class 反转链表 {
    // 迭代方法
    public ListNode reverseList1(ListNode head) {
        ListNode ans = new ListNode(0, null);
        while (head != null) {
            ans.next = new ListNode(head.val, ans.next);
            head = head.next;
        }
        return ans.next;
    }

    //递归方法
    // 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode last = reverseList(head.next);

        head.next.next = head;

        head.next = null;

        return last;
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre, cur, nxt;
        pre = null;
        cur = head;
        nxt = head.next;
        while (cur != null) {
            cur.next = pre;
            pre = cur;
            cur = nxt;
            if (nxt != null) {
                nxt = nxt.next;
            }
        }
        return pre;
    }
}
